'''
https://leetcode.cn/problems/trapping-rain-water/description/
'''

from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        l_max, r_max = [0] * n, [0] * n
        l_max[0] = height[0]
        r_max[-1] = height[-1]
        for i in range(1, n):
            l_max[i] = max(height[i], l_max[i - 1])
        for i in range(n - 2, -1, -1):
            r_max[i] = max(height[i], r_max[i + 1])

        ans = 0
        for i in range(n):
            ans += max(0, min(l_max[i], r_max[i]) - height[i])
        return ans

    def trap2(self, height: List[int]) -> int:
        n = len(height)
        r_max = [0] * n
        r_max[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            r_max[i] = max(height[i], r_max[i + 1])

        l_max = 0
        ans = 0
        for i in range(n):
            l_max = max(height[i], l_max)
            ans += min(l_max, r_max[i]) - height[i]
        return ans

    def trap3(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        l_max = r_max = 0
        ans = 0
        while l < r:
            l_max = max(height[l], l_max)
            r_max = max(height[r], r_max)
            if height[l] < height[r]:
                # ans += min(l_max, r_max) - height[l]
                ans += l_max - height[l]
                l += 1
            else:
                # ans += min(l_max, r_max) - height[r]
                ans += r_max - height[r]
                r -= 1
        return ans
